package com.algomypractice.skiplist;

import java.util.Random;

/**
 * @author: ZhouBert
 * @date: 2019/6/28
 * @description:	跳表的java实现
 * 性质：
 * (1) 由很多层结构组成，【level是通过一定的概率随机产生的】。
 * (2) 每一层都是一个【有序】的链表，默认是升序
 * (3) 最底层(Level 1)的链表【包含所有元素】。
 * (4) 如果一个元素出现在Level i 的链表中，则它在Level i 之下的链表也【都会出现】。
 * (5) 【每个节点包含两个指针】，一个指向同一链表中的下一个元素，一个指向下面一层的元素。
 * (6) 以2为间隔区分 level 时，总数小于2n
 * 比较详细的参考
 * https://blog.csdn.net/gloomysnow/article/details/51510203
 * 讲义
 * https://blog.csdn.net/pcwl1206/article/details/83512600
 *
 * 此例子的跳表结构类似：
 * MAX_Level - level
 * .
 * .
 * .
 * 3
 * 2
 * 1
 * 0
 *
 */
public class SkipList<E extends Comparable<? super E>> {
	//region	属性
	/**
	 * 跳表层数32层，定义成32层，理论上对于2^32-1个元素的查询最优
	 */
	private final int MAX_LEVEL=32;
	/**
	 * 当前跳表的有效层？？？
	 */
	private int level=0;
	/**
	 * 跳表的头部节点
	 */
	private final SkipNode<E> Header = new SkipNode<E>(MAX_LEVEL, null);
	/**
	 * 随机数发生器
	 */
	private final Random random=new Random();
	/**
	 * 自然数e
	 */
	private final double E=Math.E;
	//endregion

	//region	方法

	/**
	 * 检查跳表中是否包含val节点
	 * @param val
	 * @return
	 */
	public boolean contains(E val){
		/**
		 * cur 指向跳表头结点
		 */
		SkipNode<E> cur=Header;

		/**
		 * level指向基于当前数据量的当前层数
		 * 从顶层开始查找当前层的链表中是否包含节点node
		 */
		for (int i = level; i >= 0; i--) {
			while (cur.getNext()!=null && cur.getNext()[i].getVal().compareTo(val)>0){
				cur=cur.getNext()[i];
			}
			if(	cur.getNext()[i].getVal().equals(val)){
				return true;
			}
		}
		return false;
	}

	/**
	 * 往跳表中插入数据
	 * @param val
	 */
	public void insert(E val){
		SkipNode<E> cur=Header;
		SkipNode[] predecessors = new SkipNode[MAX_LEVEL];

		for (int i = level; i >= 0; i--) {
			cur=Header;
			while (cur.getNext()[i]!=null && cur.getNext()[i].getVal().compareTo(val)<0 ){
				cur=cur.getNext()[i];
			}
			predecessors[i]=cur;
		}
		cur = cur.getNext()[0];
		int nextLevel = randomLevel();
		/*
		 * 如果带插入节点位置是空的或者与node节点值不同 将新节点插入到跳表中
		 */
		if (cur == null || !cur.getVal().equals(val)) {
			/*
			 * 若新增一层链表
			 */
			if (nextLevel > level) {
				predecessors[nextLevel] = Header;
				level = nextLevel;
			}
			SkipNode<E> node = new SkipNode(MAX_LEVEL, val);
			for (int i = level; i >= 0; i--) {
				node.getNext()[i] = predecessors[i].getNext()[i];
				predecessors[i].getNext()[i] = node;
			}
		}
	}
	//endregion


	/**
	 * 利用随机数发生器来决定是否新增一层
	 *
	 * @return
	 */
	private int randomLevel() {
		double ins = random.nextDouble();
		int nextLevel = level;
		if (ins > E && level < MAX_LEVEL) {
			nextLevel++;
		}
		return nextLevel;
	}
}
